﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <vector>
using namespace std;
// 原题连接：https://www.nowcoder.com/practice/4af96fa010c44638a7e112abf65f7237?tpId=196&tqId=39285&ru=/exam/oj

/*
题目描述：
给定一个长度为 n 的数组a，求它的最长严格上升子序列的长度。
所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
我们定义一个序列是 严格上升 的，当且仅当该序列不存在两个下标
i
i 和
j
j 满足
i
<
j
i<j 且
a
i
≥
a
j
a
i
​
 ≥a
j
​
 。
数据范围：
0
≤
n
≤
1
0
5
0≤n≤10
5
 ，
−
1
0
9
<
=
a
[
i
]
<
=
1
0
9
−10
9
 <=a[i]<=10
9

要求：时间复杂度
O
(
n
l
o
g
n
)
O(nlogn)， 空间复杂度
O
(
n
)
O(n)
示例1
输入：
[1,4,7,5,6]
复制
返回值：
4
复制
说明：
最长上升子序列为 [1,4,5,6] ，长度为4。
*/

// 开始解题：
// 方法——贪心 + 二分
class Solution {
public:
    int LIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> len; // len[i]表示长度为i + 1的子序列中，末尾最小的元素
        for (int i = 0; i < n; i++) {
            if (len.empty() || len.back() < nums[i]) {
                len.push_back(nums[i]);
            }
            else {
                // 二分寻找插入位置
                // 从右往左找到第一个大于nums[i]的位置
                int left = 0, right = len.size() - 1;
                while (left < right) {
                    int mid = (right + left) >> 1;
                    if (len[mid] < nums[i]) {
                        left = mid + 1;
                    }
                    else {
                        right = mid;
                    }
                }
                len[left] = nums[i];
            }
        }
        return len.size();
    }
};